МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
Лабораторна робота № 1
алгоритм; властивості, параметри та характеристики
складності алгоритму.
" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
1. МЕТА РОБОТИ
проаналізувати складність заданих алгоритмів.
ТЕОРЕТИЧНІ ВІДОМОСТІ
1.1. Здавна найбільшу увагу приділяли дослідженням алгоритму з метою мінімізації
часової складності розв’язання задач. Але зміст складності алгоритму не обмежується
однією характеристикою. В ряді випадків не менше значення має складність логіки
побудови алгоритму, різноманітність його операцій, зв’язаність їх між собою. Ця
характеристика алгоритму називається програмною складністю. В теорії алгоритмів, крім
часової та програмної складності, досліджуються також інші характеристики складності,
наприклад, місткісна, але найчастіше розглядають дві з них – часову і програмну. Якщо у
кінцевому результаті часова складність визначає час розв’язання задачі, то програмна
складність характеризує ступінь інтелектуальних зусиль, що потрібні для синтезу
алгоритму. Вона впливає на витрати часу проектування алгоритму. Код програми
//to measure time it is better to run with Linux
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N1 606
#define N2 601
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
#define REPEAT_COUNT 1000000
#define REPEATOR(count, code) \
for (unsigned int indexIteration = (count); indexIteration--;){ code; }
#define TWO_VALUES_SELECTOR(variable, firstValue, secondValue) \
(variable) = indexIteration % 2 ? (firstValue) : (secondValue);
double getCurrentTime(){
clock_t time = clock();
if (time != (clock_t)-1) {
return ((double)time / (double)CLOCKS_PER_SEC);
}
return 0.; // else
}
unsigned long long int f1_GCD(unsigned long long int variableN1, unsigned long long int variableN2){
unsigned long long int returnValue = 1;
for(unsigned long long int i = 1, k = MIN(variableN1, variableN2); i <= k; i++){
if(!(variableN1 % i || variableN2 % i)){
returnValue = i;
}
}
return returnValue;
}
unsigned long long int f2_GCD(unsigned long long int a, unsigned long long int b){
for(unsigned long long int aModB;
aModB = a % b,
a = b,
b = aModB;
);
return a;
}
unsigned long long int f3_GCD(unsigned long long int a, unsigned long long int b){
if(!b){
return a;
}
return f3_GCD(b, a % b); // else
}
int main() {
unsigned long long int vN1 = N1, vN2 = N2, a = MAX(vN1, vN2), b = MIN(vN1, vN2),
vN1_ = vN1, vN2_ = vN2, a_ = a, b_ = b,
returnValue;
double startTime, endTime;
// f1_GCD
startTime = getCurrentTime();
REPEATOR(REPEAT_COUNT,
TWO_VALUES_SELECTOR(vN1, 16, vN1_);
TWO_VALUES_SELECTOR(vN2, 4, vN2_);
returnValue = f1_GCD(a, b);
)
endTime = getCurrentTime();
printf("f1_GCD return %d \r\nrun time: %dns\r\n\r\n",
returnValue,
(unsigned int)((endTime - startTime) * (double)(1000000000 / REPEAT_COUNT)));
// f2_GCD
startTime = getCurrentTime();
REPEATOR(REPEAT_COUNT,
TWO_VALUES_SELECTOR(a, 16, a_);
TWO_VALUES_SELECTOR(b, 4, b_);
returnValue = f2_GCD(a, b);
)
endTime = getCurrentTime();
printf("f2_GCD return %d \r\nrun time: %dns\r\n\r\n",
returnValue,
(unsigned int)((endTime - startTime) * (double)(1000000000 / REPEAT_COUNT)));
// f3_GCD
startTime = getCurrentTime();
REPEATOR(REPEAT_COUNT,
TWO_VALUES_SELECTOR(a, 16, a_);
TWO_VALUES_SELECTOR(b, 4, b_);
returnValue = f3_GCD(a, b);
)
endTime = getCurrentTime();
printf("f3_GCD return %d \r\nrun time: %dns\r\n\r\n",
returnValue,
(unsigned int)((endTime - startTime) * (double)(1000000000 / REPEAT_COUNT)));
printf("Press any key to continue . . .");
getchar();
return 0;
} Висновок: На даній лабораторній роботі я проаналізував складність заданих алгоритмів.
